翻訳と辞書 Words near each other ・ Propagation of light in non-inertial reference frames ・ Proof of age inquisition ・ Proof of Age Standards Scheme ・ Proof of Bertrand's postulate ・ Proof of Citizenship of the Republic of Indonesia ・ Proof of concept ・ Proof of delivery ・ Proof of Destruction ・ Proof of Existence ・ Proof of Fermat's Last Theorem ・ Proof of Fermat's Last Theorem for specific exponents ・ Proof of funds ・ Proof of Impact ・ Proof of impossibility ・ Proof of insurance ・ Proof of knowledge ・ Proof of Life ・ Proof of Life (album) ・ Proof of Life (disambiguation) ・ Proof of Life (Scott Stapp album) ・ Proof of Life (The Bill) ・ Proof of O(log*n) time complexity of union–find ・ Proof of purchase ・ Proof of Stein's example ・ Proof of the Euler product formula for the Riemann zeta function ・ Proof of the Man ・ Proof of Youth ・ Proof positive ・ Proof Positive (album) ・ Proof Positive (Greene story) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Proof of knowledge ： ウィキペディア英語版 Proof of knowledge In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds 'convincing' a verifier that the prover knows something. What it means for a machine to 'know something' is defined in terms of computation. A machine 'knows something', if this something can be computed, given the machine as an input. As the program of the prover does not necessarily spit out the knowledge itself (as is the case for zero-knowledge proofs〔Shafi Goldwasser, Silvio Micali, and Charles Rackoff. (The knowledge complexity of interactive proof-systems ). ''Proceedings of 17th Symposium on the Theory of Computation'', Providence, Rhode Island. 1985. Draft. (Extended abstract )〕) a machine with a different program, called the knowledge extractor is introduced to capture this idea. We are mostly interested in what can be proven by polynomial time bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some language in NP. Let $x$ be a language element of language $L$ in NP, and $W(x)$ the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation: $R=\; \backslash$. A proof of knowledge for relation $R$ with knowledge error $\backslash kappa$ is a two party protocol with a prover $P$ and a verifier $V$ with the following two properties: # Completeness: if $(x,w)\; \backslash in\; R$, the prover P who knows witness $w$ for $x$ succeeds in convincing the verifier $V$ of his knowledge. More formally: $\backslash Pr(P(x,w)\backslash leftrightarrow\; V(x)\; \backslash rightarrow\; 1)\; =1$ # Validity: Validity requires that the success probability of a knowledge extractor $E$ in extracting the witness, given oracle access to a possibly malicious prover $\backslash tilde\; P$, must be at least as high as the success probability of the prover $\backslash tilde\; P$ in convincing the verifier. This Property guarantees that no prover that doesn't know the witness can succeed in convincing the verifier. ==Details on the definition== This is a more rigorous definition of Validity:〔Mihir Bellare, Oded Goldreich: (On Defining Proofs of Knowledge ). CRYPTO 1992: 390–420〕 Let $R$ be a witness relation, $W(x)$ the set of all witnesses for public value $x$, and $\backslash kappa$ the knowledge error. A proof of knowledge is $\backslash kappa$-valid if there exists a polynomial-time machine $E$, given oracle access to $\backslash tilde\; P$, such that for every $\backslash tilde\; P$, it is the case that $E^(x)\; \backslash in\; W(x)\; \backslash cup\; \backslash$ and $\backslash Pr(E^(x)\; \backslash in\; W(x))\; \backslash geq\; \backslash Pr(\backslash tilde\; P(x)\backslash leftrightarrow\; V(x)\; \backslash rightarrow\; 1)\; -\; \backslash kappa(x).$ The result $\backslash bot$ signifies that the Turing machine $E$ did not come to a conclusion. The knowledge error $\backslash kappa(x)$ denotes the probability that the verifier $V$ might accept $x$, even though the prover does in fact not know a witness $w$. The knowledge extractor $E$ is used to express what is meant by the knowledge of a Turing machine. If $E$ can extract $w$ from $\backslash tilde\; P$, we say that $\backslash tilde\; P$ knows the value of $w$. This definition of the validity property is a combination of the validity and strong validity properties in.〔 For small knowledge errors $\backslash kappa(x)$, such as e.g. $2^$ or $1/\backslash mathrm(|x|)$ it can be seen as being stronger than the soundness of ordinary interactive proofs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Proof of knowledge」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.